package segement;

/**
 * 每一个节点存储的不是一个具体值，存储的是 一个数组的一部分。直到叶子节点是一个元素的数组
 * 线段树不是完全二叉树
 * 线段树是平衡二叉树
 * 堆也是平衡二叉树
 * 平衡二叉树: 最大的深度和最小的深度 之差 不超过 1
 * 对于满二叉树:  h层  一共有  2^h  - 1 个节点
 *                最后一层  h-1 层   有 2^(h-1) 个节点
 *                最后一层的节点数大致等于前面所有层节点之和
 *
 *                所以当需要存储 n个节点 那么 一般需要  n = 2^k  需要 2n
 *                最坏 n = 2^k + 1 则需要 4n
 *
 *
 *
 *                学业有待完成。。。最后一行，暂时用null代替
 */
public class Segement<E> {


    private E[] data;
    private E[] tree;

    public Segement(E[] arr){
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[])new Object[data.length << 2];
        buildSegementTree(0,0,data.length-1);
    }

    private void buildSegementTree(int treeIndex,int r,int l){
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = l + (r-l)/2;
        buildSegementTree(leftTreeIndex,l,mid);
        buildSegementTree(rightTreeIndex,mid+1,r);
        //tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
    }
    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if (index< 0||index>data.length-1) {
            throw new RuntimeException("越界");
        }
        return data[index];
    }

    private int leftChild(int index){
        return (index << 1) + 1;
    }

    private int rightChild(int index){
        return (index << 1) + 2;
    }
    public E query(int queryL,int queryR){
        if(queryL < 0 || queryL > data.length || queryR < 0 || queryR > data.length || queryL > queryR){
            throw new RuntimeException("参数违规");
        }
        return query(0,0,data.length -1,queryL,queryR);
    }

    private E query(int treeIndex,int l,int r,int queryL,int queryR){
        if (l == queryL && r == queryR) {
            return tree[treeIndex];
        }
        int mid = l + (r-l)/2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if (mid >= mid+1) {
            return query(treeIndex,mid+1,r,queryL,queryR);
        }else if(queryR <= mid){
            return query(treeIndex,queryL,mid,queryL,queryR);
        }

        E leftResult = query(leftTreeIndex,l,mid,queryL,mid);
        E rightResult = query(rightTreeIndex,mid+1,r,mid,queryR);

        return null;    // 这里需要继续往下写，暂时用null替代
    }
}
